// ==================================================
// Programmer:  Jonathan Landrum
// Date:        16 April 2012
// ==================================================
// Program:     induce.cpp
// Purpose:     Uses inductive reasoning to show that
//		a number input by the user is a
//		product of primes.
// Assumptions: 1.) The number input is a natural
//		    number.
//		2.) The number input is > 1.
// ==================================================

#include <iostream>
using namespace std;

// --------------------------------------------------
// Function prototypes
// --------------------------------------------------
void induce(int);
bool prime(int);


// --------------------------------------------------
// main():
// Calls the induce() function
// --------------------------------------------------
int main () {
	
	// Variables
	int  input = 0;
	
	// Introduce the program
	cout << endl;
	cout << "--------------------------------" << endl;
	cout << "-      Inductive Reasoning     -" << endl;
	cout << "--------------------------------" << endl;
	cout << endl;
	cout << "This program uses recursion to" << endl;
	cout << "show that any natural number > 1" << endl;
	cout << "is a product of primes.";
	cout << endl << endl;
	
	// Get user input
	while (input < 2) {
		cout << "Enter an integer to test: ";
		cin  >> input;
	}
	
	cout << endl;
	
	// Return the results
	induce(input);
	cout << endl;
	cout << "--------------------------------" << endl;
	cout << "\\\\//_ Live long and prosper." << endl;
	return (0);
} // End main


// --------------------------------------------------
// induce():
// Prints out the results of proving the number input
// is a product of primes.
// --------------------------------------------------
void induce (int n) {
	if (prime(n)) {
		cout << n << " is prime, so it is a product of a single prime." << endl;
	} else {
		cout << "In order to prove that " << n << " is a product of primes" << endl;
		if (n % 13 == 0) {
			cout << "\twe prove that " << n / 13 << " and 13 are products of primes." << endl;
			induce(n/13);
			induce(13);
			cout << "Having proven that " << n / 13 << " and 13 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 13 << " * " << 13 << endl;
		} else if (n % 11 == 0) {
			cout << "\twe prove that " << n / 11 << " and 11 are products of primes." << endl;
			induce(n/11);
			induce(11);
			cout << "Having proven that " << n / 11 << " and 11 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 11 << " * " << 11 << endl;
		} else if (n % 7 == 0) {
			cout << "\twe prove that " << n / 7 << " and 7 are products of primes." << endl;
			induce(n/7);
			induce(7);
			cout << "Having proven that " << n / 7 << " and 7 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 7 << " * " << 7 << endl;
		} else if (n % 5 == 0) {
			cout << "\twe prove that " << n / 5 << " and 5 are products of primes." << endl;
			induce(n/5);
			induce(5);
			cout << "Having proven that " << n / 5 << " and 5 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 5 << " * " << 5 << endl;
		} else if (n % 3 == 0) {
			cout << "\twe prove that " << n / 3 << " and 3 are products of primes." << endl;
			induce(n/3);
			induce(3);
			cout << "Having proven that " << n / 3 << " and 3 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 3 << " * " << 3 << endl;
		} else if (n % 2 == 0) {
			cout << "\twe prove that " << n / 2 << " and 2 are products of primes." << endl;
			induce(n/2);
			induce(2);
			cout << "Having proven that " << n / 2 << " and 2 are products of primes," << endl;
			cout << "\twe condlude that " << n << " = " << n / 2 << " * " << 2 << endl;
		}
		cout << "\tis a product of primes." << endl;
	}
}


// --------------------------------------------------
// prime():
// Determines if a number is prime
// --------------------------------------------------
bool prime (int n) {
	// Variables
	bool result;
	int  i;
	
	// Do work
	if (n <= 1) {
		result = false; // 1 is not prime
		
	} else if ((n == 2) || (n == 3)) {
		result = true; // Hard code 2 and 3
		
	} else if (n % 2 == 0) {
		result = false; // Get rid of evens
		
		/* All other cases are out, so now we check
		 to see if n is divisible by the odd
		 numbers from 3 on. */
	} else {
		i = 3;
		result = true; // Assume it's prime, then prove
		
		while (true) {
			/* If i^2 is not a root of n, or if
			 n % i == 0. (Won't be larger than
			 the square.) */
			if ((i * i > n) || (n % i == 0))
				break;
			i += 2; // Iterate by 2 to get odds
		} // End while
		
		// Record the answer
		if (i * i > n)
			result = true;
		else
			result = false;
	} // End if
	
	
	// Return the answer
	return result;
}